// 步骤:
// 找到链表中点（快慢指针法）。
// 递归排序左右两部分。
// 合并两个有序链表。


class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function sortList(head) {
  if (!head || !head.next) {
    return head; // 空链表或单节点直接返回
  }

  // 1. 找到链表中点（快慢指针）
  let slow = head;
  let fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  const mid = slow.next;
  slow.next = null; // 切断链表

  // 2. 递归排序左右两部分
  const left = sortList(head);
  const right = sortList(mid);

  // 3. 合并两个有序链表
  return merge(left, right);
}


function merge(l1, l2) {
  const dummy = new ListNode(0);
  let curr = dummy;

  while (l1 && l2) {
    if (l1.val < l2.val) {
      curr.next = l1;
      l1 = l1.next;
    } else {
      curr.next = l2;
      l2 = l2.next;
    }
    curr = curr.next;
  }

  // 连接剩余部分
  curr.next = l1 || l2;
  return dummy.next;
}

// 测试代码
const head = new ListNode(4);
head.next = new ListNode(2);
head.next.next = new ListNode(1);
head.next.next.next = new ListNode(3);

const sortedList = sortList(head);

// 打印排序后的链表
let current = sortedList;
while (current) {
  console.log(current.val);
  current = current.next;
}
// 输出: 1 -> 2 -> 3 -> 4